package a09_贪心算法;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <p>
 * a19_划分字母区间复习3
 * </p>
 *
 * @author flyduck
 * @since 2025/4/25
 */
public class a19_划分字母区间复习3 {
    public static void main(String[] args) {
        System.out.println(partitionLabels("ababcbacadefegdehijhklij"));
    }
    //ababcbacadefegdehijhklij
    //a=8,
    // b=5,
    // c=7,
    // d=14,
    // e=15,
    // f=11, g=13, h=19, i=22, j=23, k=20, l=21
    //满足：i超过当前遍历过元素的最大索引就可以截取
    public static List<Integer> partitionLabels(String s) {
        char[] chars = s.toCharArray();
        Map<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < chars.length; i++) {
            map.put(chars[i],i);
        }

        List<Integer> result = new ArrayList<>();
        int leftIdx = 0;
        int rightIdx = 0;
        int maxIdx = 0;
        while (leftIdx < chars.length && rightIdx < chars.length){
            maxIdx = Math.max(maxIdx, map.get(chars[rightIdx]));
            if(rightIdx >= maxIdx){
                result.add(rightIdx - leftIdx + 1);
                leftIdx = rightIdx + 1;
                rightIdx = leftIdx;
            }else {
                rightIdx++;
            }
        }
        return result;
    }
}
